package com.gitee.ywj1352.算法.真实;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

public class 前缀和 {

    int subarraySum(int[] nums, int k) {
        int n = nums.length;
        // 构造前缀和
        int[] sum = new int[n + 1];
        sum[0] = 0;
        for (int i = 0; i < n; i++)
            sum[i + 1] = sum[i] + nums[i];

        int ans = 0;
        // 穷举所有子数组
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < i; j++)
                // sum of nums[j..i-1]
                if (sum[i] - sum[j] == k)
                    ans++;

        return ans;
    }


    int subarraySum2(int[] nums, int k) {
        int n = nums.length;
        // map：前缀和 -> 该前缀和出现的次数
        HashMap<Integer, Integer> preSum = new HashMap<>();
        // base case
        preSum.put(0, 1);
        int ans = 0, sum0_i = 0;
        for (int num : nums) {
            sum0_i += num;
            // 这是我们想找的前缀和 nums[0..j]
            int sum0_j = sum0_i - k;
            // 如果前面有这个前缀和，则直接更新答案
            if (preSum.containsKey(sum0_j))
                ans += preSum.get(sum0_j);
            // 把前缀和 nums[0..i] 加入并记录出现次数
            preSum.put(sum0_i,
                    preSum.getOrDefault(sum0_i, 0) + 1);
        }
        return ans;
    }

    public static int shortestSubarray(int[] nums, int k) {
        int[] A = nums;
        int K = k;
        long[] arr = new long[A.length + 1];
        for (int i = 0; i < A.length; i++) {
            arr[i + 1] = arr[i] + A[i];
            if (A[i] >= K) return 1;
        }//得到前缀和数组
        int res = Integer.MAX_VALUE;
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            while (!queue.isEmpty() && arr[i] <= arr[queue.peekLast()]) {
                Integer idx = queue.removeLast();
              //  System.out.println(idx);
            }
            while (!queue.isEmpty() && arr[i] - arr[queue.peekFirst()] >= K) {
                Integer poll = queue.poll();
                System.out.println(poll);

                res = Math.min(res, poll);
            }
            queue.add(i);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, -1, 3, 4};
        int i = shortestSubarray(nums, 5);
        System.out.println(i);

    }
}
